package leetcode_801_900;

import java.util.*;

public class LeeCode_815_wrong {
    public static void main(String[] args) {
        System.out.println(numBusesToDestination(new int[][]{{1, 2, 7}, {3, 6, 7}}, 1, 6));
        System.out.println(numBusesToDestination(new int[][]{{1, 2, 7}, {3, 6, 7}, {4, 5, 6}}, 3, 7));
        System.out.println(numBusesToDestination(new int[][]{{1, 2}, {2}}, 1, 2));
        System.out.println(numBusesToDestination(new int[][]{{1, 2, 3}, {2,3,5}, {3,4,5}, {4, 5, 6}}, 1, 6));
        System.out.println(numBusesToDestination(new int[][]{{1, 7}, {3, 5}}, 5, 3));
    }
    private static int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target)
            return 0;
        int n = routes.length;
        Map<Integer, List<Integer>> tmp = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int num : routes[i]) {
                if (tmp.containsKey(num)){
                    tmp.get(num).add(i);
                }else {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    tmp.put(num, list);
                }
            }
        }
        boolean[][] used = new boolean[n][n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (Integer key : tmp.keySet()) {
            List<Integer> list = tmp.get(key);
            int l = list.size();
            for (int i = 0; i < l; i++) {
                for (int j = i + 1; j < l; j++) {
                    int x = list.get(i), y = list.get(j);
                    if (used[x][y])
                        continue;
                    if (map.containsKey(x)){
                        map.get(x).add(y);
                    }else {
                        List<Integer> son = new ArrayList<>();
                        son.add(y);
                        map.put(x, son);
                    }
                    if (map.containsKey(y)){
                        map.get(y).add(x);
                    }else {
                        List<Integer> son = new ArrayList<>();
                        son.add(x);
                        map.put(y, son);
                    }
                    used[x][y] = true;
                    used[y][x] = true;
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        int step = 0;
        List<Integer> sss = tmp.get(source);
        Set<Integer> ss = new HashSet<>(sss);
        int start = sss.get(0);
        Set<Integer> targets = new HashSet<>(tmp.get(target));
        boolean[] vis = new boolean[n];
        Deque<int[]> deque = new ArrayDeque<>();
        deque.add(new int[]{start, -1, start});
        boolean flag = false;
        while (!deque.isEmpty()){
            if (flag)
                break;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int[] p = deque.pop();
                int now = p[0], fa = p[1], from = p[2];
                if (sss.contains(now)){
                    from = now;
                }
                if (targets.contains(now)){
                    ans = step + 1;
                    ans += from == start ? 0 : -1;
                    flag = true;
                    break;
                }
                vis[now] = true;
                for (Integer next : map.get(now)) {
                    if (next == fa || vis[next])
                        continue;
                    deque.offer(new int[]{next, now, from});
                }
            }
            step++;
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}